package com.leetcode.tree;

import java.util.*;

/**
 * @author ymy
 * @date 2021年12月31日 11:08
 */
class Code01 {
    public static void main(String[] args) {
        Code01 code01 = new Code01();
        Integer[] arr = new Integer[]{1,2,3,4,5,6,7,8,9};
        TreeNode tree = code01.createTree(arr);
        System.out.println("前序遍历：");
        code01.preorderTraversal(tree);
        System.out.println();
        System.out.println("中序遍历：");
        code01.mediumOrderTraversal(tree);
        System.out.println();
        System.out.println("后序遍历：");
        code01.postorderTraversal(tree);
        System.out.println();
        System.out.println("前序遍历-栈：");
        code01.preorderTraversalStack(tree);
    }
    /**
     * 构建二叉树
     * @author ymy
     * @date 2021/12/31 11:25
     * @param arr
     * @return com.leetcode.tree.Code01.TreeNode
     */
    public TreeNode createTree(Integer[] arr){
        LinkedList<TreeNode> list = new LinkedList();
        // 将一个数组的值依次转换为Node节点
        for(Integer num : arr){
            list.add(new TreeNode(num));
        }
        // 对前n-1个父节点按照父节点与孩子节点的数字关系建立二叉树
        for(int index = 0;index<arr.length/2 -1;index++){
            //左节点
            list.get(index).left = list.get(index*2 + 1);
            //右节点
            list.get(index).right = list.get(index*2 + 2);
        }
        // 最后一个父节点:因为最后一个父节点可能没有右孩子，所以单独拿出来处理
        int lastParentIndex = arr.length/2 -1;
        // 左孩子
        list.get(lastParentIndex).left = list.get(lastParentIndex*2+1);
        //判断是否存在右孩子
        if(arr.length % 2 == 1){
            list.get(lastParentIndex).right = list.get(lastParentIndex * 2 +2);
        }
        return list.get(0);
    }

    /**
     * 前序遍历递归实现
     * @author ymy
     * @date 2021/12/31 11:26
     */
    public void preorderTraversal(TreeNode node){
        if(node == null){
            return;
        }
        System.out.print(node.data+" ");
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }
    /**
     * 前序遍历栈实现
     * @author ymy
     * @date 2021/12/31 11:26
     */
    public void preorderTraversalStack(TreeNode node){
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()){
            TreeNode pop = stack.pop();
            list.add(pop.data);
            if(pop.right != null){
                stack.push(pop.right);
            }
            if(pop.left != null){
                stack.push(pop.left);
            }
        }
        System.out.println(list);
    }
    /**
     * 中序遍历
     * @author ymy
     * @date 2021/12/31 11:26
     */
    public void mediumOrderTraversal(TreeNode node){
        if(node == null){
            return;
        }
        mediumOrderTraversal(node.left);
        System.out.print(node.data+" ");
        mediumOrderTraversal(node.right);
    }
    /**
     * 后序遍历
     * @author ymy
     * @date 2021/12/31 11:26
     */
    public void postorderTraversal(TreeNode node){
        if(node == null){
            return;
        }
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.print(node.data+" ");
    }

    /**
     * 层序遍历
     * @author ymy
     * @date 2021/12/31 11:26
     */
    public void levelTraversal(TreeNode node){
        Queue<TreeNode> que = new LinkedList<TreeNode>();
    }

    public class TreeNode{
        Integer data;
        TreeNode left;
        TreeNode right;
     public TreeNode(Integer data) {
         this.data = data;
     }

     @Override
     public String toString() {
         return "TreeNode{" +
                 "data=" + data +
                 ", left=" + left +
                 ", right=" + right +
                 '}';
     }
 }
}
